package com.moon.leetcode;

// 5791. 统计子岛屿
//给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖
//直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
//
// 如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那
//么我们称 grid2 中的这个岛屿为 子岛屿 。
//
// 请你返回 grid2 中 子岛屿 的 数目 。
//
//
//
// 示例 1：
//
// 输入：grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], gri
//d2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
//输出：3
//解释：如上图所示，左边为 grid1 ，右边为 grid2 。
//grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。
//
//
// 示例 2：
//
// 输入：grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], gri
//d2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
//输出：2
//解释：如上图所示，左边为 grid1 ，右边为 grid2 。
//grid2 中标红的 1 区域是子岛屿，总共有 2 个子岛屿。
//
//
//
//
// 提示：
//
//
// m == grid1.length == grid2.length
// n == grid1[i].length == grid2[i].length
// 1 <= m, n <= 500
// grid1[i][j] 和 grid2[i][j] 都要么是 0 要么是 1 。
//
// Related Topics 深度优先搜索 并查集
// 👍 6 👎 0
public class No5791_countSubIslands {
    int[][] grid1;
    int[][] grid2;
    boolean b;
    int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    int m;
    int n;

    public int countSubIslands(int[][] grid1, int[][] grid2) {
        this.grid1 = grid1;
        this.grid2 = grid2;
        this.m = grid1.length;
        this.n = grid1[0].length;
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid2[i][j] == 1 && grid1[i][j] == 1) {
                    b = true;
                    checkIsland(i, j);
                    ans += b ? 1 : 0;
                }
            }
        }
        return ans;
    }

    private void checkIsland(int i, int j) {
        int tmp = grid2[i][j];
        if (tmp == 1) {
            grid2[i][j] = 3;
            if (grid1[i][j] == 0) {
                b = false;
            }
            for (int k = 0; k < 4; k++) {
                int l = i + dir[k][0];
                int r = j + dir[k][1];
                if (0 <= l && l < m && 0 <= r && r < n) {
                    int nextTmp = grid2[l][r];
                    if (nextTmp != 1) {
                        continue;
                    }
                    checkIsland(l, r);
                }
            }
        }
    }
}
